package cn.fxzhang.leetcode.no00;

/**
 * 27. 移除元素
 *
 * 类型：数组/双指针
 * 题解：双指针，一个指向头部存放元素，一个指向尾部，用尾部的元素来填充头部
 * 时间复杂度：O(N)
 * 空间复杂度：O(1)
 *
 * 提交记录(1/1)：
 * 执行用时: 0 ms, 击败了100.00%
 * 内存消耗: 36.9 MB, 击败了80.05%
 * @author 张晓帆
 * @date 2021/4/19
 */
public class P0027_Remove_Element {

    public int removeElement(int[] nums, int val) {
        int tail = nums.length-1;
        int i;
        for (i=0; i<=tail; i++){
            if (nums[i] == val){
                while (tail>=i && nums[tail] == val) tail--;
                if (tail <= i){
                    return i;
                }
                nums[i] = nums[tail];
                tail--;
            }
        }
        return i;
    }

}
